package com.chj.chuji.tijie05;

//https://zhuanlan.zhihu.com/p/115474184
public class ChkPalindrome {
	public static class ListNode {
		int val;
		ListNode next = null;

		ListNode(int val) {
			this.val = val;
		}
	}

	public static boolean chkPalindrome(ListNode A) {
		if (A == null || A.next == null) {
			return true;
		}
		ListNode n1 = A;
		ListNode n2 = A;
		// 找中间节点
		while (n2.next != null && n2.next.next != null) {
			n1 = n1.next;
			n2 = n2.next.next;
		}
		// 反转中间节点后面的链表
		ListNode n3 = null;
		n2 = n1.next;
		n1.next = null;
		while (n2 != null) {
			n3 = n2.next;
			n2.next = n1;
			n1 = n2;
			n2 = n3;
		}

		// 比较
		n2 = A;
		while (n1 != null && n2 != null) {
			if (n1.val != n2.val) {
				return false;
			}
			n1 = n1.next;
			n2 = n2.next;
		}

		return true;
	}

	public static void printCircularList(String str, ListNode head) {

		if (head == null) {
			System.out.println(str + " List: " + head + " ");
			return;
		}
		System.out.print(str + " List: " + head.val + " ");
		ListNode cur = head.next;
		while (cur != head && cur != null) {
			System.out.print(cur.val + " ");
			cur = cur.next;
		}
		System.out.println("|| header-> " + head.val);
	}

	public static boolean isPalindrome3(ListNode head) {
		if (head == null || head.next == null)
			return true;
		ListNode n1 = head;
		ListNode n2 = head;
		while (n2.next != null && n2.next.next != null) {
			n1 = n1.next;
			n2 = n2.next.next;
		}

		System.out.println("===111");
		printCircularList("n1", n1);
		printCircularList("n2", n2);
		printCircularList("A", head);
		System.out.println("===111");

		n2 = n1.next; // n2 -> 右半部分第一个node
		n1.next = null; // mid.next -> null

		// convert right part 局部结构：n1 -> n2 -> n3 -> ni -> ...
		ListNode lastTemp = null;
		ListNode midNode = null;
		ListNode lastNode = null;
		ListNode backNode = null;
		ListNode rightHead = null;
		ListNode leftHead = null;
		ListNode lastNextNode = null;

		midNode = n1;
		rightHead = n2;

		lastTemp = RecoverNode(midNode, rightHead);

		lastNode = lastTemp; // 此时n2为空，n1为last node ,用n3记录下来便与恢复结构
		backNode = lastTemp; // 记录下来便与恢复结构
		leftHead = head; // n2 为left part first node
		boolean res = true; // 保存结果，最后才返回

		// check 回文
		while (lastNode != null && leftHead != null) {
			if (lastNode.val != leftHead.val) {
				res = false;
				break;
			}
			lastNode = lastNode.next;
			leftHead = leftHead.next;
		}

		// recover List
		lastNextNode = backNode.next;
		backNode.next = null;

		RecoverNode(backNode, lastNextNode);
		printCircularList("AAA", head);

		return res;
	}

	private static ListNode RecoverNode(ListNode midNode, ListNode rightHead) {
		// TODO Auto-generated method stub
		ListNode headTemp = null;
		while (rightHead != null) {
			headTemp = rightHead.next; // save n2的 next node
			rightHead.next = midNode; // 改变n2指向
			midNode = rightHead; // 移动n1
			rightHead = headTemp; // 移动n2
		}

		return midNode;
	}

	public static void main(String[] args) {
//		例如：1 ->2 -> 1，返回true。
//		1 -> 2 -> 2 -> 1，返回true。
//		15 -> 6 -> 15，返回true。
//		1 -> 2 -> 3，返回 false 
		ListNode head2 = new ListNode(1);
		head2.next = new ListNode(2);
		head2.next.next = new ListNode(3);
		head2.next.next.next = new ListNode(4);
		head2.next.next.next.next = new ListNode(3);
		head2.next.next.next.next.next = new ListNode(2);
		head2.next.next.next.next.next.next = new ListNode(1);
		printCircularList("test", head2);
		System.out.println(chkPalindrome(head2));
		ListNode head5 = new ListNode(1);
		head5.next = new ListNode(2);
		head5.next.next = new ListNode(3);
		head5.next.next.next = new ListNode(4);
		head5.next.next.next.next = new ListNode(3);
		head5.next.next.next.next.next = new ListNode(2);
		head5.next.next.next.next.next.next = new ListNode(1);
		printCircularList("test5", head5);
		System.out.println(isPalindrome3(head5));
		System.out.println();

		ListNode head3 = new ListNode(1);
		head3.next = new ListNode(2);
		head3.next.next = new ListNode(2);
		head3.next.next.next = new ListNode(1);
		printCircularList("test", head3);
		System.out.println(chkPalindrome(head3));
		ListNode head6 = new ListNode(1);
		head6.next = new ListNode(2);
		head6.next.next = new ListNode(2);
		head6.next.next.next = new ListNode(1);
		printCircularList("test6", head6);
		System.out.println(isPalindrome3(head6));
		System.out.println();

		ListNode head4 = new ListNode(1);
		head4.next = new ListNode(2);
		head4.next.next = new ListNode(3);
		printCircularList("test", head4);
		System.out.println(chkPalindrome(head2));
	}
}
